#include <iostream>
#include <vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
class Solution
{
public:
    /**
     * @brief
     * 执行用时：
        112 ms
        , 在所有 C++ 提交中击败了
        18.33%
        的用户
        内存消耗：
        29.3 MB
        , 在所有 C++ 提交中击败了
        94.49%
        的用户
     *
     * @param list1
     * @param list2
     * @return vector<string>
     */
    vector<string> findRestaurant(vector<string> &list1, vector<string> &list2)
    {
        int indexSum = list1.size() + list2.size() - 2;

        vector<string> ret;
        for (int i = 0; i < list1.size(); i++)
        {
            auto it = find(list2.begin(), list2.end(), list1[i]);
            if (it != list2.end())
            {
                int j = it - list2.begin();
                if (i + j < indexSum)
                {
                    ret.clear();
                    indexSum = i + j;
                    ret.push_back(list1[i]);
                }
                else if (i + j == indexSum)
                {
                    ret.push_back(list1[i]);
                }
            }
        }
        return ret;
    }

    vector<string> findRestaurant_2(vector<string> &list1, vector<string> &list2)
    {
        unordered_map<string, int> index;
        for (int i = 0; i < list1.size(); i++)
        {
            index[list1[i]] = i;
        }

        vector<string> ret;
        int indexSum = INT_MAX;
        for (int i = 0; i < list2.size(); i++)
        {
            if (index.count(list2[i]) > 0)
            {
                int j = index[list2[i]];
                if (i + j < indexSum)
                {
                    ret.clear();
                    ret.push_back(list2[i]);
                    indexSum = i + j;
                }
                else if (i + j == indexSum)
                {
                    ret.push_back(list2[i]);
                }
            }
        }
        return ret;
    }
};
int main()
{
    Solution s;
    vector<string> list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
    vector<string> list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
    vector<string> ans = s.findRestaurant(list1, list2);
    for (string a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
